package com.zp.self.module.level_4_算法练习.算法.排序;

import org.junit.Test;

import java.util.Arrays;

/**
@author By ZengPeng
    可参考：https://blog.csdn.net/yeahPeng11/article/details/117912723
    将得比较系统哦,点赞、

    算法稳定性：
    如果待排序的序列中存在值相等的元素，结果排序之后，相等元素之间原有的先后顺序不变。
    例如3，7，2，7，8排序之后为2，3，7，7，8其中两个7的先后次序没有发生变化则称该算法是文档的排序算法。
    （一般会优先选择具有稳定性的算法）
 */
public class I_冒泡排序_O_n2 {
    @Test
    public void main(){
        System.out.println(Arrays.toString(maoPao(new int[]{12,5,6,4,7,8,5,101,0,72})));
    }
    /**
     题目： 冒泡排序：时间：O(n*n) 、空间：O(1)、顺序稳定

     分析：冒泡:从arr[0],一直两两比上去,大的往上冒:->第一轮 arr[length-1]就是最大的了
     **/
    private int[] maoPao(int[] num) {
        for (int i = 0; i < num.length; i++) {
            for (int j = 0; j < num.length-i-1; j++) {
                if(num[j]>num[j+1]){
                    num[j]= num[j]^num[j+1];
                    num[j+1]= num[j]^num[j+1];
                    num[j]= num[j]^num[j+1];
                }
            }
        }
        return num;
    }

    //优化：如果某次排序中没有发生交换，则可以结束排序
    public int[] bubbleSort(int[] arr){
        for (int i = 0; i < arr.length; i++) {
            boolean flag = true;
            //相临元素的比较
            for (int j = 0; j < arr.length - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    int tmp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = tmp;
                    flag = false;//说明要排序
                }
            }
            if(flag) return arr;//说明此时数据已经有序 直接返回即可
        }
        return arr;
    }

}
